Modern industrial processes often include one or more time critical functions that are controlled by centralized or distributed control systems. This may include functions performed in automated manufacturing and assembly processes, computer networking, content distribution, and communication systems, to name but a few. Modern wireless communication systems are particularly relevant because such systems include numerous functions that must be carried out to support operations such as channel allocation, live communication, and call hand-off, which across a communication network are executed millions of times per second.
At the simplest level, a function is an operation that involves a set of specific actions (e.g. processing on a data input to generate a data output). An algorithm is one example of a function. See, Cormen et al, “Introduction to Algorithms”, 3rd edition, MIT Press, 2009, for an explanation of algorithms. Communication systems are built around numerous functions. For example, one such function is the scheduling procedure in a multi-user wireless 4G communication system. See, Dahlman, Parkvall, Sköld, “4G LTE/LTE-Advanced for Mobile Broadband”, Academic Press, 2011, for an explanation of 4G LTE communications systems.
In systems like communication systems, many functions are performed repeatedly and continuously. Also, such systems may have multiple simultaneous active instances of a function at a given moment in time (e.g. the parallel execution of the same algorithm with different inputs on multiple cores in a multicore processing unit). Typically, it takes a finite amount of time to perform the actions of the function. This time is referred to as the processing time. This time may be deterministic, that is, the same for a given input, or it may be random.
Throughout this disclosure and in the claims that follow the term “node” is used in the context of functions. Actions such as data processing, data input or output in a function often takes place in or are executed by a node. A node can be a processor, a processor core, a digital signal processor (DSP), a circuit board, a computer, a radio base station, combinations of these, or some other suitable structure. In other words, nodes may exist on many hardware levels and on many levels of abstraction.
A distributed function is a kind of function that involves actions occurring in a plurality of nodes, where at least two of the nodes are physically and/or logically separated. Two nodes are distributed if the output of one node cannot be immediately input to the other node. In a distributed function, there is a positive time delay D between the output of one node and the corresponding input to the next node. As used in this disclosure and in the claims that follow, the physical and/or logical link between two nodes is referred to as the backhaul and the positive time delay for data to travel over the backhaul is referred to as the backhaul delay. Backhaul delays may be deterministic or random. If deterministic, the backhaul delay may be known or unknown. Otherwise, if the backhaul delay is random, then its statistical properties (or a part of them) may be known or unknown. For example, the backhaul delay may be random, but the average delay and variance may be known with at least some accuracy. In one example, the backhaul is over the Internet where the delay is random because packets are subject to variations in delay time known as jitter.
Functions, including distributed functions, typically start at a certain time, called the starting time. Time in this context may be discrete or continuous. For example, in an LTE communication system, time can be discretely measured in sub-frames, since transmissions need to be done according to the sub-frame timing and pattern. The time that a function finishes its operations is referred to as the function completion time. The completion of a function can involve the output of a result and can also signify that the final action of the function is finished. For example, a sorting algorithm completes when the input has been sorted and stored in memory. Another example is a scheduling procedure in an LTE communication network, which can be seen as completed when the scheduling decision has been properly distributed.
An exemplary distributed function is illustrated in FIG. 1. The function 100 of FIG. 1 is comprised of two nodes, 1 and 2, interconnected by a backhaul link. The dotted line surrounding the function 100 is purely symbolic and is not intended to define any physical boundary. In this function 100, after the function starts, some processing occurs in node one that generates an output. The output travels over the backhaul to node 2 where further processing occurs before the function completes.
The time between the starting time and completion time, which includes the processing time at each node and the backhaul delay, is called the duration of the function. The duration of the function may also be deterministic or random due to processing and/or backhaul delays. The time-line of a distributed function such as that shown in FIG. 1 is illustrated in FIG. 2.
FIG. 2 provides an example timeline for a distributed function with two distributed nodes. Operation of the function starts in node 1 at starting time T0. While in node 1, actions 1.1, 1.2 and 1.3 are performed to complete the sub-function process of node 1. This results in an output that is sent to node 2 over the backhaul. After a backhaul delay, node 2 receives its input and proceeds with action 2.1. The function completes when action 2.1 is finished. The time between starting time in node 1 and completion time in node 2 is measured on the timeline marked duration.
Communication system functions are often time-critical. A time-critical function is one that must be completed before a certain completion deadline expires. If the completion occurs after the completion deadline expires, then a function failure occurs. A function failure can be more or less severe in different systems, however, generally it has a negative impact on the system. Similarly, if a time-critical function completes in time, then a function success occurs. Note that a function failure or success in the context of this disclosure relates to function completion before the completion deadline, not to any other notion of failure or success.
Given a starting time and a completion deadline, a time-critical function has a maximum duration called the maximum duration. If the function takes a longer time (the duration) than the maximum duration, then a function failure occurs. One example of a time-critical function is the downlink scheduling of a certain sub-frame in an LTE communication system. The scheduling decision needs to be made and properly distributed in the system before the sub-frame starts, so that the decision and the data can be properly transmitted in the designated sub-frame. If the scheduling and transmission preparation of the sub-frame does not complete before the sub-frame starts, then there is a function failure. Such a failure likely results in wasted radio resources and reduced system performance.
FIG. 3 is a timeline that illustrates data flow in a two node distributed communication system with backhaul delay usable with various embodiments of the invention. The example shown in FIG. 3 is a function that performs downlink scheduling in an LTE communication system. In this exemplary function, the scheduling of sub-frame n is performed in node 1 and node 2 is the transmitter. The two nodes are connected with a backhaul link.
The downlink scheduling function of sub-frame n begins in node 1 at the point on timeline for node 1 marked as the starting time. After a delay due to the required processing time to make a scheduling decision, the decision is send from node 1 to node 2 over the backhaul. The time difference between when the decision is send from node 1 and when it is received by node 2 is the backhaul delay Node 2 receive the decision at the time after the function starting time equal to node 1's processing time plus the backhaul delay. Node 2 also requires a certain amount of processing time to prepare and complete the transmission based on the received scheduling decision. Node 2's operations cease at the completion time indicated on the timeline for node 2. The scheduling decision needs to be received in node 2 with sufficient time before sub-frame n, so that there is adequate time to prepare the transmission. If this happens, it results in a function success. If the completion time of the function is after the completion deadline, for example due unusually long backhaul delay, then there is a function failure.
In another example, consider the random access procedure in LTE. A UE transmits a preamble in a certain sub-frame (the starting time). The response must be transmitted by the network within a certain configurable time-window (before the end of the time-window, i.e. the completion deadline). If the UE does not receive the response within this time-window, it considers the random access attempt a failure (a function failure). This is illustrated in FIG. 4, where the function is distributed and performed in three nodes (Node 1, Node 2 and Node 3). The starting time is for example the beginning of the subframe where a random access preamble may be transmitted by UEs. The preamble detection is performed in the receiver in Node 1. A preamble detection result is then sent over a backhaul to Node 2, where a scheduler is located. The response is scheduled and the scheduling decision is sent over the backhaul to Node 3, where a transmitter is located. The transmission of the response needs to be prepared before the actual transmission. This needs to be completed before the start of the subframe where the response is to be transmitted (the completion deadline), otherwise a function failure occurs.
FIG. 4 is a timeline that illustrates data flow in a three node distributed communication system with backhaul delay usable with various embodiments of the invention. In FIG. 4, node 1 is an uplink receiver, node 2 is a scheduler and node 3 is a downlink transmitter. The nodes are connected with backhaul links. The function in this example are part of a random access procedure such as that employed in an LTE communication system. A random access preamble is detected in node 1. The detection results are sent over the backhaul to node 2. The time between when the detection results are sent from node 1 and when they are received at node 2 is a positive backhaul delay identified as d1 in FIG. 4. After receipt, node 2 performs a scheduling process that results in a scheduling decision suing the detection results received from node 1. Node 2 sends the scheduling decision over the backhaul to the transmitter at node 3. The time between when node 2 sends the scheduling decision and when it is received at node 3 is backhaul delay d2. The transmitter and node 3 prepares the transmission using the received scheduling decision and completes its transmission at the end of the completion time shown on the node 3 timeline. If a response can be transmitted by node 3 before the corresponding completion deadline (e.g. the last sub-frame in the corresponding random access response window in LTE), then the function is deemed to have succeeded. Otherwise, if the completion time of the function is after the completion deadline, the function is deemed to have failed and in the LTE example of FIG. 4, the random access procedure cannot proceed.
For systems such as those depicted in FIGS. 2-4, it would be desirable to have a mechanism to optimize the system to achieve an acceptable target function failure rate without having to explicitly estimate the statistical or other properties of a random or unknown function duration.